package org.cllib.math;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Stack;

public class BigNumber {
	private List<Digit> digits = new ArrayList<Digit>();
	private int radix = 10;
	private boolean negative;

	public BigNumber(String s) {
		if (s.startsWith("-")) {
			s = s.substring(1);
			negative = true;
		}

		for (int i = 0; i < s.length(); i++) {
			Digit d = new Digit(new Range(radix - 1));
			d.setValue(Integer.parseInt(String.valueOf(s.charAt(i))));

			digits.add(d);
		}

		check(s);
	}

	public BigNumber(BigNumber bn) {
		this.negative = bn.negative;
		this.radix = bn.radix;
		this.digits.addAll(bn.digits);

//		if (Long.parseLong(this.toString()) != Long.parseLong(bn.toString())) {
//			throw new IllegalStateException("fail to copy");
//		}

		check(bn);
	}

	private void check(BigNumber bn) {
		if (digits.size() <= 0) {
			throw new IllegalArgumentException(
					"unable to create BigNumber from BigNumber [" + bn + "]");
		}
	}

	private void check(String s) {
		if (digits.size() <= 0) {
			throw new IllegalArgumentException(
					"unable to create BigNumber from input[" + s + "]");
		}
	}

	private BigNumber() {

	}

	public int getNumberOfDigits() {
		return digits.size();
	}

	public BigNumber increase() {
		final BigNumber one = new BigNumber("1");
		BigNumber result = this.sub(one);
		this.negative = result.negative;
		this.digits = new ArrayList<Digit>(result.digits);
		return this;
	}

	public BigNumber decrease() {
		final BigNumber one = new BigNumber("1");
		BigNumber result = this.sub(one);
		this.negative = result.negative;
		this.digits = new ArrayList<Digit>(result.digits);
		return this;
	}

	public static BigNumber abs(BigNumber bn) {
		BigNumber result = new BigNumber(bn);
		result.negative = false;
		return result;
	}

	public BigNumber add(BigNumber bn) {
		boolean negative = false;
		if (this.negative == bn.negative) {
			negative = this.negative;
		} else {
			BigNumber b1 = this.negative ? bn : this;
			BigNumber b2 = this.negative ? this : bn;
			return b1.sub(abs(b2));
		}

		BigNumber b1 = abs(this);
		BigNumber b2 = abs(bn);

		Stack<Digit> stack = new Stack<Digit>();

		int i = b1.getNumberOfDigits() - 1, j = b2.getNumberOfDigits() - 1;
		int carry = 0;
		for (; i >= 0 && j >= 0; i--, j--) {
			Digit id = b1.digits.get(i);
			Digit jd = b2.digits.get(j);

			int sum = id.getCurrent() + jd.getCurrent() + carry;

			if (sum >= radix) {
				carry = 1;
			} else {
				carry = 0;
			}

			sum = sum % radix;

			Digit cd = new Digit(new Range(radix - 1));
			cd.setValue(sum);

			stack.push(cd);
		}

		if (i >= 0) {
			while (i >= 0) {
				Digit d = b1.digits.get(i);
				int sum = d.getCurrent() + carry;

				if (sum >= radix) {
					carry = 1;
				} else {
					carry = 0;
				}

				sum = sum % radix;

				Digit cd = new Digit(new Range(radix - 1));
				cd.setValue(sum);

				stack.push(cd);

				i--;
			}
		}

		if (j >= 0) {
			while (j >= 0) {
				Digit d = b2.digits.get(j);
				int sum = d.getCurrent() + carry;

				if (sum >= radix) {
					carry = 1;
				} else {
					carry = 0;
				}

				sum = sum % radix;

				Digit cd = new Digit(new Range(radix - 1));
				cd.setValue(sum);

				stack.push(cd);

				j--;
			}
		}

		if (carry != 0) {
			Digit d = new Digit(new Range(radix - 1));
			d.setValue(carry);

			stack.push(d);
		}

		BigNumber result = new BigNumber();

		while (!stack.isEmpty()) {
			result.digits.add(stack.pop());
		}

		result.negative = negative;

		BigNumber zero = new BigNumber("0");

		if (abs(result).eq(zero)) {
			result.negative = false;
		}

		return result;
	}

	public boolean gt(BigNumber bn) {
		if (this.negative == bn.negative) {
			int nd1 = this.getNumberOfDigits();
			int nd2 = bn.getNumberOfDigits();

			if (nd1 > nd2) {
				return this.negative ? false : true;
			} else if (nd1 < nd2) {
				return this.negative ? true : false;
			} else {
				if (eq(bn)) {
					return false;
				}

				for (int i = 0; i < nd1; i++) {
					if (this.digits.get(i).getCurrent() < bn.digits.get(i)
							.getCurrent()) {
						return this.negative ? true : false;
					}
					if (this.digits.get(i).getCurrent() > bn.digits.get(i)
							.getCurrent()) {
						return this.negative ? false : true;
					}
				}
			}
		} else {
			if (this.negative) {
				return false;
			} else {
				return true;
			}
		}
		return false;
	}

	public boolean lt(BigNumber bn) {
		if (this.negative == bn.negative) {
			int nd1 = this.getNumberOfDigits();
			int nd2 = bn.getNumberOfDigits();

			if (nd1 < nd2) {
				return this.negative ? false : true;
			} else if (nd1 > nd2) {
				return this.negative ? true : false;
			} else {
				if (eq(bn)) {
					return false;
				}
				for (int i = 0; i < nd1; i++) {
					if (this.digits.get(i).getCurrent() > bn.digits.get(i)
							.getCurrent()) {
						return this.negative ? true : false;
					}
					if (this.digits.get(i).getCurrent() < bn.digits.get(i)
							.getCurrent()) {
						return this.negative ? false : true;
					}
				}
			}
		} else {
			if (this.negative) {
				return true;
			} else {
				return false;
			}
		}
		return false;
	}

	public boolean gteq(BigNumber bn) {
		return gt(bn) || eq(bn);
	}

	public boolean lteq(BigNumber bn) {
		return lt(bn) || eq(bn);
	}

	public boolean eq(BigNumber bn) {
		if (this.negative == bn.negative) {
			int nd1 = this.getNumberOfDigits();
			int nd2 = bn.getNumberOfDigits();
			if (nd1 == nd2) {
				for (int i = 0; i < nd1; i++) {
					if (this.digits.get(i).getCurrent() != bn.digits.get(i)
							.getCurrent()) {
						return false;
					}
				}
				return true;
			}
		}
		return false;
	}

	public BigNumber sub(BigNumber bn) {
		boolean negative = false;
		if (this.negative != bn.negative) {
			BigNumber b1 = abs(this);
			BigNumber b2 = abs(bn);

			BigNumber result = b1.add(b2);
			result.negative = this.negative;

			return result;
		}

		Stack<Digit> stack = new Stack<Digit>();

		int borrow = 0;

		BigNumber b1 = abs(this);
		BigNumber b2 = abs(bn);

		if (this.lt(bn)) {
			negative = true;
		}

		if (b1.lt(b2)) {
			BigNumber t = b1;
			b1 = b2;
			b2 = t;
		}

		int i = b1.getNumberOfDigits() - 1;
		int j = b2.getNumberOfDigits() - 1;

		for (; i >= 0 && j >= 0; i--, j--) {
			Digit id = b1.digits.get(i);
			Digit jd = b2.digits.get(j);

			int sum = id.getCurrent() + borrow - jd.getCurrent();
			if (sum < 0) {
				borrow = -1;
				sum += radix;
			} else {
				borrow = 0;
			}

			Digit d = new Digit(new Range(radix - 1));
			d.setValue(sum);

			stack.push(d);
		}

		if (j >= 0) {
			throw new IllegalStateException("subtrahend longer than minuhend");
		}

		if (i >= 0) {
			while (i >= 0) {
				Digit id = b1.digits.get(i);

				int sum = id.getCurrent() + borrow;
				if (sum < 0) {
					borrow = -1;
					sum += radix;
				} else {
					borrow = 0;
				}

				Digit d = new Digit(new Range(radix - 1));
				d.setValue(sum);

				stack.push(d);

				i--;
			}
		}

		while (stack.peek().getCurrent() == 0 && stack.size() > 1) {
			stack.pop();
		}

		if (borrow != 0) {
			borrow += radix;

			Digit d = new Digit();
			d.setValue(borrow);

			stack.push(d);
		}

		BigNumber result = new BigNumber();
		while (!stack.isEmpty()) {
			result.digits.add(stack.pop());
		}

		result.negative = negative;

		BigNumber zero = new BigNumber("0");
		if (abs(result).eq(zero)) {
			result.negative = false;
		}
		return result;
	}

	public BigNumber mul(BigNumber bn) {
		boolean negative = false;

		BigNumber zero = new BigNumber("0");

		BigNumber sum = zero;
		final BigNumber multiplicand = abs(this);
		final BigNumber multiplier = abs(bn);

		BigNumber c = new BigNumber(multiplier);
		while (c.gt(zero)) {
			sum = sum.add(multiplicand);
			c = c.decrease();
		}

		if (this.negative != bn.negative) {
			negative = true;
		}

		sum.negative = negative;
		return sum;
	}

	public BigNumber div(BigNumber bn) {
		BigNumber zero = new BigNumber("0");
		if (bn.eq(zero)) {
			throw new ArithmeticException("divided by zero");
		}

		BigNumber r = new BigNumber(abs(this));
		BigNumber subtrahend = abs(bn);

		BigNumber c = zero;

		while (r.gteq(subtrahend)) {
			r = r.sub(subtrahend);
			c = c.increase();
		}
		boolean negative = false;
		if (this.negative != bn.negative) {
			negative = true;
		}
		c.negative = negative;
		return c;
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		if (negative) {
			sb.append('-');
		}
		for (int i = 0; i < digits.size(); i++) {
			sb.append(digits.get(i).getCurrent());
		}
		return sb.toString();
	}

	public static void main(String[] args) {
		Random r = new Random();
		for (int i = 0; i < 10000; i++) {
			long i1 = r.nextInt(100);
			long i2 = r.nextInt(100);

			BigNumber b1 = new BigNumber(String.valueOf(i1));
			BigNumber b2 = new BigNumber(String.valueOf(i2));

			if (i1 < i2 != b1.lt(b2)) {
				throw new IllegalStateException("lt fail for [i1 = " + i1
						+ " i2 = " + i2 + "] " + b1.lt(b2));
			}

			if (i1 <= i2 != b1.lteq(b2)) {
				throw new IllegalStateException("lteq fail for [i1 = " + i1
						+ " i2 = " + i2 + "] " + b1.lteq(b2));
			}

			if (i1 > i2 != b1.gt(b2)) {
				throw new IllegalStateException("gt fail for [i1 = " + i1
						+ " i2 = " + i2 + "] " + b1.gt(b2));
			}

			if (i1 >= i2 != b1.gteq(b2)) {
				throw new IllegalStateException("gteq fail for [i1 = " + i1
						+ " i2 = " + i2 + "] " + b1.gteq(b2));
			}

			if (i1 == i2 != b1.eq(b2)) {
				throw new IllegalStateException("eq fail for [i1 = " + i1
						+ " i2 = " + i2 + "] " + b1.eq(b2));
			}

			BigNumber sum = b1.add(b2);
			try {
				long suml = Long.parseLong(sum.toString());
				if (i1 + i2 != suml) {
					throw new IllegalStateException("add fail for [i1 = " + i1
							+ " i2 = " + i2 + " i1 + i2 = " + (i1 + i2)
							+ " sum = " + sum + "]");
				}
			} catch (NumberFormatException e) {
				System.out.println("fail to parse sum [" + sum + "]");
			}

			BigNumber diff = b1.sub(b2);
			try {
				long diffl = Long.parseLong(diff.toString());
				if (i1 - i2 != diffl) {
					throw new IllegalStateException("sub fail for [i1 = " + i1
							+ " i2 = " + i2 + " i1 - i2 = " + (i1 - i2)
							+ " diff = " + diff + "]");
				}
			} catch (NumberFormatException e) {
				System.out.println("fail to parse difference [" + diff + "]");
			}

			BigNumber product = b1.mul(b2);
			try {
				long productl = Long.parseLong(product.toString());
				if (i1 * i2 != productl) {
					throw new IllegalStateException("mul fail for [i1 = " + i1
							+ " i2 = " + i2 + " i1 * i2 = " + (i1 * i2)
							+ " product = " + product + "]");
				}
			} catch (NumberFormatException e) {
				System.out.println("fail to parse product [" + product + "]");
			}
			if (i2 != 0) {
				BigNumber quotient = b1.div(b2);
				try {
					long quotientl = Long.parseLong(quotient.toString());
					if (i1 / i2 != quotientl) {
						throw new IllegalStateException("div fail for [i1 = "
								+ i1 + " i2 = " + i2 + " i1 / i2 = "
								+ (i1 / i2) + " quotient = " + quotient + "]");
					}
				} catch (NumberFormatException e) {
					System.out.println("fail to parse quotient [" + quotient
							+ "]");
				}
			}

			System.out.println("running " + i);
		}
		System.out.println("ok");
	}
}
